package leetcode_ago.bin_tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的层序遍历
 * 用二维数组保存：一层用一个小集合存储，最后大集合存储所有层
 * 注意：
 * 1.队列为空遍历完毕
 * 2.队列中保存的都是下一层要处理的元素，即一层处理完下一层要处理的元素已经正好保存在队列中了
 */
public class Num102_LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//根节点入队
        //队列不为空时持续执行
        while(!queue.isEmpty()){
            //使用一个temp数组保存当前层要处理的元素
            List<Integer> temp=new ArrayList<>();
            //当前队列元素个数，也就是当前层元素个数
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                //依次从队列中取出队首元素并存储到集合中
                TreeNode cur=queue.poll();
                temp.add(cur.val);
                //将下一层的元素进行入队
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
            }
            //一层循环完将本层元素的集合加入二维数组ret中
            ret.add(temp);
        }
        return ret;
    }
}
